import functools


class Solution:
    _COLOR = ["R", "Y", "B", "G", "W"]  # 颜色列表
    _INDEX = {"R": 0, "Y": 1, "B": 2, "G": 3, "W": 4}  # 颜色下标

    def findMinStep(self, board: str, hand: str) -> int:
        ans = self.dfs(board=board, hand=hand)
        return ans if ans <= 5 else -1

    @functools.lru_cache(None)
    def dfs(self, board: str, hand: str):
        count1 = [board.count(color) for color in self._COLOR]
        count2 = [hand.count(color) for color in self._COLOR]

        # 剪枝1：处理从数量上来说无法构成的情况
        for i in range(5):
            if count1[i] > 0 and count1[i] + count2[i] < 3:
                return float("inf")

        ans = 0

        # 剪枝2：当某种颜色的球在桌面上只有连续的2个时，那么可以先处理掉这个球
        while True:
            # 寻找并优先消除符合剪枝条件的球
            change = False
            for i in range(5):
                if count1[i] == 2 and self._COLOR[i] * 2 in board:
                    board = board.replace(self._COLOR[i] * 2, "")
                    hand = hand.replace(self._COLOR[i], "")  # 手中这个颜色的球已经没有意义，可以全部清除
                    ans += 1
                    change = True
                    break

            # 清理当前需要消除的球（达到3个）
            board = self.update(board)

            # 如果已经没有符合剪枝条件的球，则结束当前步骤
            if not change:
                break

        # 剪枝2A：如果已经桌面上已经没有球，则返回结果
        if not board:
            return ans

        count1 = [board.count(color) for color in self._COLOR]

        # 剪枝3：如果桌面上只有一种颜色的球，那么直接填球补上即可
        if len([num for num in count1 if num > 0]) == 1:
            return ans + max(3 - len(board), 0)

        count2 = [hand.count(color) for color in self._COLOR]

        # 将相同字母合并到一起
        lst = []
        for i, ch in enumerate(board):
            if not lst or ch != lst[-1][0]:
                lst.append(ch)
            else:
                lst[-1] += ch

        # 遍历所有可能的添加球（添加到可以形成连续3个）情况
        surplus = float("inf")  # 剩余部分需要的步数
        for i in range(len(lst)):
            ch = lst[i][0]
            num = len(lst[i])
            need = 3 - num

            # 剪枝4：需要支持手中还有足够让当前短添加到连续3个的球
            if count2[self._INDEX[ch]] < need:
                continue

            # 剪枝5：需要桌面上剩下的同颜色的球及手上同颜色的球还可以支持被消除
            if count1[self._INDEX[ch]] > num and count1[self._INDEX[ch]] + count2[self._INDEX[ch]] < 6:
                continue

            new_board = "".join(lst[:i]) + "".join(lst[i + 1:])
            new_board = self.update(new_board)

            new_hand = list(hand)
            for _ in range(need):
                new_hand.remove(ch)

            # print(board, hand, "->", ch, need, "->", new_board, "".join(new_hand))

            surplus = min(surplus, need + self.dfs(new_board, "".join(new_hand)))

        return ans + surplus

    @staticmethod
    def update(board: str):
        """清理当前需要消除的球（达到3个）"""
        while True:
            change = False
            now, num = "", 0
            for ch in board:
                if ch != now:
                    if num >= 3:
                        board = board.replace(now * num, "")
                        change = True
                        break
                    else:
                        now, num = ch, 1
                else:
                    num += 1
            if num >= 3:
                board = board.replace(now * num, "")
                change = True
            if not change:
                break
        return board


if __name__ == "__main__":
    print(Solution().findMinStep(board="WRRBBW", hand="RB"))  # -1
    print(Solution().findMinStep(board="WWRRBBWW", hand="WRBRW"))  # 2
    print(Solution().findMinStep(board="G", hand="GGGGG"))  # 2
    print(Solution().findMinStep(board="RBYYBBRRB", hand="YRBGB"))  # 3

    # 测试用例
    print(Solution().findMinStep(board="RRWWRRW", hand="WWRRR"))  # 2

    # 测试用例20
    print(Solution().findMinStep(board="RRWWRRW", hand="WR"))  # -1

    # 测试用例24
    print(Solution().findMinStep(board="WR", hand="WWRR"))  # 4

    # 测试用例28
    print(Solution().findMinStep(board="RRWWRRBBRR", hand="WB"))  # 2

    # 测试用例29
    print(Solution().findMinStep(board="RRWWRRBBR", hand="WB"))  # -1

    # 自制用例
    print(Solution().findMinStep(board="RRWRRBBRR", hand="WWB"))  # 3
